Efficient and reliable delivery of media content is increasingly important with the growth in popularity of downloading music and video over the Internet. Video is very appealing because it offers a much richer user experience than static images and text. It is more interesting, for example, to watch a video clip of a winning touchdown or a Presidential speech than it is to read about the event in stark print. Unfortunately, video data is significantly larger than other data types commonly delivered over the Internet. As an example, one second of uncompressed video data may consume one or more Megabytes of data. Delivering such large amounts of data over error-prone networks, such as the Internet and wireless networks, presents difficult challenges in terms of both efficiency and reliability.
To promote efficient delivery, video data is typically encoded prior to delivery to reduce the amount of data actually being transferred over the network. Image quality is lost as a result of the compression, but such loss is generally tolerated as necessary to achieve acceptable transfer speeds. In some cases, the loss of quality may not even be detectable to the viewer.
Video compression is well known. One common type of video compression is a motion-compensation-based video coding scheme, which is used in such coding standards as MPEG-1, MPEG-2, MPEG-4, H.261, H.263, and H.264.
In general video coding systems, motion estimation efficiently eliminates temporal redundancy between adjacent frames. Unfortunately, motion estimation is also responsible for consuming a large amount of computation resources in a video coder. This is especially true for the video coding standard H.264, where motion estimation accounts for most of the encoder complexity. This standard uses a macroblock structure with seven different block sizes, and performs fractional pixel searching at ¼-pixel accuracy. Simplifying the motion estimation process in such video coding processes would be helpful for real-time applications.
In video coding standard H.264, the motion estimation process is separated into two phases: (1) integer pixel motion estimation and (2) fractional pixel motion estimation. Generally, integer pixel motion estimation is responsible for most of the computational cost of the whole motion estimation. However, with the development of fast integer motion estimation algorithms, the computational cost of integer pixel motion estimation has been significantly reduced. Fast integer motion compensation algorithms are described in the following articles:                Z. Zhou, M. T. Sun and Y. F. Hsu, “Fast variable block-size motion estimation algorithms based on merge and split procedures for H.264/MPEG-4 AVC,” Proc. of ISCAS 2004, pp. 725-728, May 2004. Other        C. Zhu, X. Lin, L. P. Chau, K. P. Lim, H. A. Ang, and C. Y. Ong, “A novel hexagon-based search algorithm for fast block motion estimation,” Proc. of ICASSP 2001, vol. 3, pp 1593-96, May 2001.        A. Tourapis, “Enhanced predictive zonal search for single and multiple frame motion estimation,” In Proc. of VCIP 2002, pp. 1069-79, Jan. 2002.        Z. B. Chen, P. Zhou, and Y. He, “Fast integer pel and fractional pel motion estimation for JVT,” JVT-F017, 6th meeting: Awaji, Japan, 5-13 Dec. 2002.        
While fractional pixel motion estimation has traditionally accounted for less of the computational cost, and with the advance of better techniques for integer pixel motion estimation, the computational cost of fractional pixel motion estimation is becoming comparable to that of integer pixel motion estimation and hence significant to the whole estimation process. In some cases, fractional pixel motion estimation can account for more computational costs than integer pixel motion estimation.
Accordingly, there is a need to improve fractional pixel motion estimation to thereby simplify the entire motion estimation process in video coding.